/*
	File:    	SimpleQueue.c
	Package: 	Apple CarPlay Communication Plug-in.
	Abstract: 	n/a 
	Version: 	450.14
	
	Disclaimer: IMPORTANT: This Apple software is supplied to you, by Apple Inc. ("Apple"), in your
	capacity as a current, and in good standing, Licensee in the MFi Licensing Program. Use of this
	Apple software is governed by and subject to the terms and conditions of your MFi License,
	including, but not limited to, the restrictions specified in the provision entitled ”Public 
	Software”, and is further subject to your agreement to the following additional terms, and your 
	agreement that the use, installation, modification or redistribution of this Apple software
	constitutes acceptance of these additional terms. If you do not agree with these additional terms,
	please do not use, install, modify or redistribute this Apple software.
	
	Subject to all of these terms and in consideration of your agreement to abide by them, Apple grants
	you, for as long as you are a current and in good-standing MFi Licensee, a personal, non-exclusive 
	license, under Apple's copyrights in this original Apple software (the "Apple Software"), to use, 
	reproduce, and modify the Apple Software in source form, and to use, reproduce, modify, and 
	redistribute the Apple Software, with or without modifications, in binary form. While you may not 
	redistribute the Apple Software in source form, should you redistribute the Apple Software in binary
	form, you must retain this notice and the following text and disclaimers in all such redistributions
	of the Apple Software. Neither the name, trademarks, service marks, or logos of Apple Inc. may be
	used to endorse or promote products derived from the Apple Software without specific prior written
	permission from Apple. Except as expressly stated in this notice, no other rights or licenses, 
	express or implied, are granted by Apple herein, including but not limited to any patent rights that
	may be infringed by your derivative works or by other works in which the Apple Software may be 
	incorporated.  
	
	Unless you explicitly state otherwise, if you provide any ideas, suggestions, recommendations, bug 
	fixes or enhancements to Apple in connection with this software (“Feedback”), you hereby grant to
	Apple a non-exclusive, fully paid-up, perpetual, irrevocable, worldwide license to make, use, 
	reproduce, incorporate, modify, display, perform, sell, make or have made derivative works of,
	distribute (directly or indirectly) and sublicense, such Feedback in connection with Apple products 
	and services. Providing this Feedback is voluntary, but if you do provide Feedback to Apple, you 
	acknowledge and agree that Apple may exercise the license granted above without the payment of 
	royalties or further consideration to Participant.
	
	The Apple Software is provided by Apple on an "AS IS" basis. APPLE MAKES NO WARRANTIES, EXPRESS OR 
	IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY 
	AND FITNESS FOR A PARTICULAR PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS USE AND OPERATION ALONE OR
	IN COMBINATION WITH YOUR PRODUCTS.
	
	IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, INCIDENTAL OR CONSEQUENTIAL DAMAGES 
	(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	PROFITS; OR BUSINESS INTERRUPTION) ARISING IN ANY WAY OUT OF THE USE, REPRODUCTION, MODIFICATION 
	AND/OR DISTRIBUTION OF THE APPLE SOFTWARE, HOWEVER CAUSED AND WHETHER UNDER THEORY OF CONTRACT, TORT
	(INCLUDING NEGLIGENCE), STRICT LIABILITY OR OTHERWISE, EVEN IF APPLE HAS BEEN ADVISED OF THE 
	POSSIBILITY OF SUCH DAMAGE.
	
	Copyright (C) 2017 Apple Inc. All Rights Reserved. Not to be used or disclosed without permission from Apple.
*/

#include "SimpleQueue.h"
#include "CommonServices.h"
#include "AtomicUtils.h"
#include "LogUtils.h"

#include CF_HEADER
#include CF_RUNTIME_HEADER
#include LIBDISPATCH_HEADER


#define SimpQPostError(ERR) FigSignalError(ERR, "")

//===========================================================================================================================
//	Logging
//===========================================================================================================================

ulog_define( SimpleQueue, kLogLevelNotice, kLogFlags_Default, "SimpleQueue", NULL );
#define sq_ulog( LEVEL, ... )		ulog( &log_category_from_name( SimpleQueue ), ( LEVEL ), __VA_ARGS__ )	


struct opaqueSimpleQueue {
	CFRuntimeBase	base; // Must be first field

	int32_t	capacity; // numSlots == capacity+1
	int32_t	readIndex;
	int32_t	writeIndex;
	void	*queueData[1];  // First of many... structure variably sized.
};



static void simpQFinalize(CFTypeRef cf)
{
	(void) cf;
}

//////////////// SimpQ CF Runtime Class Initialization

static CFTypeID			sSimpleQueueID		= _kCFRuntimeNotATypeID;
static CFRuntimeClass	sSimpleQueueClass;
static dispatch_once_t	gSimpleQueueInitOnce = 0;

static void registerSimpleQueueType(void *inContext)
{
	(void)inContext;
	
	sSimpleQueueClass.version				= 0;
	sSimpleQueueClass.className				= "SimpleQueue";
	sSimpleQueueClass.init					= NULL; // simpQInit;
	sSimpleQueueClass.copy					= NULL;
	sSimpleQueueClass.finalize				= simpQFinalize;
	sSimpleQueueClass.equal					= NULL; // pointer equality only
	sSimpleQueueClass.hash					= NULL; // hash to pointer identity
	sSimpleQueueClass.copyFormattingDesc	= NULL;
	sSimpleQueueClass.copyDebugDesc			= NULL;
	
	sSimpleQueueID = _CFRuntimeRegisterClass( &sSimpleQueueClass );
}


CFTypeID SimpleQueueGetTypeID()
{
	dispatch_once_f( &gSimpleQueueInitOnce, NULL, registerSimpleQueueType );
	
	return sSimpleQueueID;
}

static void SimpleQueueRelease(
	SimpleQueueRef queue)
{
	if (queue)
		CFRelease(queue);
}


OSStatus SimpleQueueCreate(
	CFAllocatorRef allocator,
	int32_t capacity,
	SimpleQueueRef *queueOut)
{
	OSStatus err = kNoErr;
	SimpleQueueRef queue = NULL;
	size_t	extra = 0;
	
	if (!queueOut || !capacity) {
		sq_ulog(kLogLevelError, "Required parameter missing\n");
		err = kSimpleQueueError_RequiredParameterMissing;
		goto bail;
	}
	
	if (capacity < 0) {
		sq_ulog(kLogLevelError, "Capacity is negative!\n");
		err = kSimpleQueueError_ParameterOutOfRange;
		goto bail;
	}
	
	// Compute the size of our structure, which needs to have one more element than
	// the capacity passed in;  this is easy because we already reserve one with the
	// declaration of our structure.
	extra = sizeof(struct opaqueSimpleQueue) + (capacity * sizeof(void *)) - sizeof(CFRuntimeBase);

	queue = (SimpleQueueRef)_CFRuntimeCreateInstance( allocator, SimpleQueueGetTypeID(), extra, NULL );
	if (!queue) {
		sq_ulog(kLogLevelError, "allocation failed\n");
		err = kSimpleQueueError_AllocationFailed;
		goto bail;
	}
	
	// This would normally be done in simpQInit, but there we don't know how big we are.
	memset(((char*)queue) + sizeof(CFRuntimeBase), 0, extra);
	
	queue->capacity = capacity;
	
bail:
	if (err) {
		// deallocate everything we managed to set up...
		SimpleQueueRelease(queue);
		queue = NULL;
	}
	if (queueOut)
		*queueOut = queue;
	return err;
}

static void simpQSetReadIndex(SimpleQueueRef queue, int32_t newReadIndex);
static void simpQSetWriteIndex(SimpleQueueRef queue, int32_t newWriteIndex);

OSStatus SimpleQueueEnqueue(SimpleQueueRef queue, const void *element)
{
	OSStatus err = kNoErr;
	int32_t newWriteIndex;
	
	if (!queue || !element) {
		sq_ulog(kLogLevelError, "Parameter missing!\n");
		err = kSimpleQueueError_RequiredParameterMissing;
		goto bail;
	}
	
	newWriteIndex = (queue->writeIndex + 1) % (queue->capacity+1);
	if (newWriteIndex == queue->readIndex) {
		sq_ulog(kLogLevelError, "Queue is full, cannot add more elements!\n");
		err = kSimpleQueueError_QueueIsFull;
		goto bail;
	}
	
	queue->queueData[queue->writeIndex] = (void *)element;
	
	simpQSetWriteIndex( queue, newWriteIndex );

bail:
	return err;
}


const void * SimpleQueueDequeue(SimpleQueueRef queue)
{
	void *element = NULL;
	
	if (!queue) {
		sq_ulog(kLogLevelError, "Parameter missing!\n");
		goto bail;
	}

	if ( queue->readIndex == queue->writeIndex ) {
		// queue is empty
		goto bail;
	}
	
	element = queue->queueData[queue->readIndex];
	
	simpQSetReadIndex(queue, (queue->readIndex + 1) % (queue->capacity+1));
	
bail:	
	return element;
}


const void * SimpleQueueGetHead(SimpleQueueRef queue)
{
	void *element = NULL;
	
	if (!queue) {
		sq_ulog(kLogLevelError, "Parameter missing!\n");
		goto bail;
	}

	if ( queue->readIndex == queue->writeIndex ) {
		// queue is empty
		goto bail;
	}
	
	element = queue->queueData[queue->readIndex];
	
bail:	
	return element;
}


OSStatus SimpleQueueReset(SimpleQueueRef queue)
{
	OSStatus err = kNoErr;
	
	if (!queue) {
		sq_ulog(kLogLevelError, "Parameter missing!\n");
		err = kSimpleQueueError_RequiredParameterMissing;
		goto bail;
	}
	
	queue->readIndex = 0;
	queue->writeIndex = 0;
	
bail:
	return err;
}

int32_t SimpleQueueGetCapacity(SimpleQueueRef queue)
{
	int32_t capacity = 0;
	
	if (!queue)
		goto bail;
	
	capacity = queue->capacity;
	
bail:
	return capacity;
}

int32_t SimpleQueueGetCount(SimpleQueueRef queue)
{
	int32_t count = 0;
	
	if (!queue)
		goto bail;
	
	{
		// Read 'em up once, so they don't get updated during your computation and you get a confused answer.
		int32_t readIndex = queue-> readIndex;
		int32_t writeIndex = queue-> writeIndex;

		if (readIndex == writeIndex)
			count = 0;
		else if (readIndex < writeIndex)
			count = writeIndex - readIndex;
		else
			count = (queue->capacity+1 - readIndex) + writeIndex;
	}
bail:
	return count;
}

static void simpQSetReadIndex(SimpleQueueRef queue, int32_t newReadIndex)
{
	atomic_read_write_barrier();
	queue->readIndex = newReadIndex;
	atomic_read_write_barrier();
}

static void simpQSetWriteIndex(SimpleQueueRef queue, int32_t newWriteIndex)
{
	atomic_read_write_barrier();
	queue->writeIndex = newWriteIndex;
	atomic_read_write_barrier();
}
